package gold.digger;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC475 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        public int findRadius(int[] houses, int[] heaters) {
            //找到每个房屋位置所需要的最小半径的最大值
            int res = 0;
            int n = heaters.length;
            Arrays.sort(houses);
            Arrays.sort(heaters);

            for (int house : houses) {
                //二分法找不小于house的第一个值
                int left = 0, right = n;
                while (left < right) {
                    int mid = left + (right - left) / 2;
                    if (house > heaters[mid]) left = mid + 1;
                    else right = mid;
                }
                int dist1 = (right == 0) ? Integer.MAX_VALUE : Math.abs(house - heaters[right - 1]);
                int dist2 = (right == n) ? Integer.MAX_VALUE : Math.abs(house - heaters[right]);
                res = Math.max(res, Math.min(dist1, dist2));
            }
            return res;
        }
    }


    public void run() {
        Solution solution = new Solution();
        List<Integer> list = new ArrayList<>();
        System.out.println(solution.toString());
    }

    public static void main(String[] args) throws Exception {
        LC475 an = new LC475();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
